1. Field of the Invention
This invention relates in general to electronic circuit design, and more particularly, to layout of a detailed grid point interconnect for integrated circuits.
2. Description of Related Art
The process of creating a complex integrated circuit (IC) chip design or a Printed Circuit Board (PCB) requires a wiring process that connects the inputs and outputs of each component within the design. This process is typically one of the last steps in the overall design process, so the designer is always under time pressure to finish the wiring process very quickly. Moreover, the designer wants the wiring process to optimize the circuit performance and reduce the noise interactions on the IC chip or PCB.
The IC chip and PCB designs of today contain up to 4 billion grid points across their topology, where the grid points are intersections of a three-dimensional mesh that is used as a construct to make the interconnections required by the IC chip or PCB. A "pin" is a set of grid points, not necessarily contiguous, that are defined to be electrically connected to each other. A "net" consists of pins, plus interconnect wiring that connects the pins to each other. The interconnect wiring is a sequential set of grid points such that each pair of grid points in the sequence is adjacent. The final net becomes an interconnection from one point on an IC chip to another point on the IC chip. The net should be of minimal length and may be constrained because of other design factors, e.g., noise tolerance, speed, etc., so a given net may have to be separated by a certain distance from other nets on the IC chip or PCB. Further, the design factors for a given net may include a width factor, where the net must have a width greater than one grid point, for current carrying capabilities or other reasons.
Large "nets" that connect components can be contained in an average area of less than 15 thousand grid points, and the average connection is in the range of 100 to 200 grid pins. Millions of nets per IC chip or PCB must be traced out through these grid points.
Creating optimal solutions to these large problems with today's CPU power and state-of-the-art software takes days or weeks to get usable results. The wiring process typically takes on the order of n.sup.2 in time, where n is the number of grid points for the length of the path. As designs get larger, the time to complete the wiring process will take an increasingly longer time. Further, long run times discourage optimization, resulting in interconnects that may exceed a maximum length and result in poor design operation or fail due to noise problems.
When the problem is partitioned into sub areas through hierarchy or simple area partitioning, the resulting solution is not globally optimized and results in longer paths for the final net interconnects. Further, area partitioning does not allow for finding and repairing local problems, nor does it allow for weighting of interconnects on a global scale.
There is a need, then for a suitable approach to the wiring process. There is also a need for a solution that reduces the time taken to solve the wiring problem. Further, there is a need for a solution that takes less time but still optimizes the wiring process. There is also a need for finding localized problems quickly for manual intervention if necessary. There is also a need for allowing dynamic weight changes for interconnect and grid point propagation. There is also a need for allowing dynamic grid point propagation blocking.